package com.example.demo.lc;

/**
 * @Description 删除倒数n的链表节点
 * @Author wzh
 * @Date 2022/6/11 10:56 下午
 * @Version 1.0
 */
public class Leetcode19 {
    public static void main(String[] args) {
        ListNode l5 = new ListNode(5);
        ListNode l4 = new ListNode(4,l5);
        ListNode l3 = new ListNode(3,l4);
        ListNode l2 = new ListNode(2,l3);
        ListNode head = new ListNode(1,l2);
        ListNode listNode = removeNthFromEnd(head, 2);
        //ListNode listNode = removeNthFromEnd1(head, 2);

        while (listNode != null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    /**
     * 获取长度-移除
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode tmp = new ListNode(0,head);
        ListNode cur = tmp;
        int lenth = getLenth(head);
        for (int i = 1; i < lenth-n+1; i++) {
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return tmp.next;
    }

    private static int getLenth(ListNode head) {
        int lenth = 0;
        while (head != null){
            lenth++;
            head = head.next;
        }
        return lenth;
    }

    /**
     * 回溯法
     */
    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        int traverse = traverse(head, n);
        if(traverse == n){
            return head.next;
        }
        return head;
    }

    private static int traverse(ListNode head, int n) {
        if(head == null){
            return 0;
        }
        int num = traverse(head.next, n);
        if(num == n){
            head.next = head.next.next;
        }
        return num+1;
    }


}
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}



